// 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。
// 一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

// 示例 1:

// 输入:
// 11110
// 11010
// 11000
// 00000

// 输出: 1
// 示例 2:

// 输入:
// 11000
// 11000
// 00100
// 00011

// 输出: 3

#include <vector>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int res{0};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1' && !visited[i][j]) { // 没有访问过的岛屿
                    DFS(grid, visited, i, j);
                    ++res;
                }
            }
        }
        return res;
    }
    void DFS(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (x < 0 || x >= grid.size() || // 越界
            y < 0 || y >= grid[0].size() || // 越界
            grid[x][y] != '1' || // 不是岛屿
            visited[x][y]) // 访问过
            return;
        visited[x][y] = true;
        DFS(grid, visited, x+1, y);
        DFS(grid, visited, x-1, y);
        DFS(grid, visited, x, y+1);
        DFS(grid, visited, x, y-1);
    }
};

/* 把岛变成水
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        vector<vector<char>> temp_grid{grid};
        int m = temp_grid.size();
        int n = temp_grid[0].size();
        int res{0};
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (temp_grid[i][j] == '1') {
                    ++res;
                    dfs(temp_grid, i, j, m, n);
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<char>>& grid, int i, int j, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
        grid[i][j] = '0';
        dfs(grid, i+1, j, m, n);
        dfs(grid, i-1, j, m, n);
        dfs(grid, i, j+1, m, n);
        dfs(grid, i, j-1, m, n);
    }
};

class UnionFind {
public:
    UnionFind(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (grid[i][j] == '1') {
                    parent.push_back(i*n + j);
                    ++count;
                } else {
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }
    int getCount() {
        return count;
    }
    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }
    void unite(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
            --count;
        }
    }
private:
    vector<int> parent{};
    vector<int> rank{};
    int count{0};
};

/* 并查集 union-find
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size();
        int n = grid[0].size();
        UnionFind uf(grid);
        int res{0};
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i-1 >= 0 && grid[i-1][j] == '1') {
                        uf.unite(i * n + j, (i-1) * n + j);
                    }
                    if (i+1 < m && grid[i+1][j] == '1') {
                        uf.unite(i * n + j, (i+1) * n + j);
                    }
                    if (j-1 >= 0 && grid[i][j-1] == '1') {
                        uf.unite(i * n + j, i * n + j - 1);
                    }
                    if (j+1 < n && grid[i][j+1] == '1') {
                        uf.unite(i * n + j, i * n + j + 1);
                    }
                }
            }
        }
        return uf.getCount();
    }
};